import scipy.sparse as sp
import numpy

"""
A class implements random walk as described in 
"N. Craswell and M. Szummer, Random walks on the click graph, SIGIR 2007."

Two types of walks are implemented: backward walking and forward walking.

J.He 
06-27-11

"""

class random_walk: 
	A = sp.csr_matrix([0])#the transition matrix
	size = 0

	def load_transition_matrix(self, mat):
		self.size = mat.shape 
		self.A = mat
		normalizer = numpy.sum(self.A.toarray(), 1)
		tmp = []
		for i in range(self.A.shape[0]):
			if float(normalizer[i])>0:
				tmp.append(self.A.toarray()[i]/float(normalizer[i]))
			else:
				tmp.append(self.A.toarray()[i])
		self.A = sp.csr_matrix(tmp)

	"""
	forward walk for n steps
	the transition matrix contains:
	A = 
	[p(q1|q1) p(q2|q1)
	 p(q1|q2) p(q2|q2)]
	
	To forward walk, initialize a vector with starting propbability
	p(q_i|q*), where q* is the outside node, q_i is the node inside
	the graph

	Example:
	let s = [1, 0]: i.e.,starting from q1
	
	Do one step transition:
	s*A = 
	[p(q1|q*)*p(q1|q1)+p(q2|q*)*p(q1|q2) p(q1|q*)*p(q2|q1)+p*(q2|q*)*p(q2|q2)]
	= [p(q1|q*) p(q2|q*)] 

	at the end of the n-step transition, the matrix contains
	the probability of starting from p1, end in p_x
	
	Note: the final result is a row vector
	"""
	def forward_walk(self, start_prob, steps):
		#initialize a result matrix
		init = start_prob*self.A #step 1
		for s in range(steps-1):
			init = init*self.A
		return init

	
	"""
	backward walking
        the transition matrix contains:
        A = 
        [p(q1|q1) p(q2|q1)
         p(q1|q2) p(q2|q2)]

	Initialize a vector with the probability that the walk ends at p(q*|q_x) 
	where q* is the node outside the graph, q_x are the nodes connected to q*
	from the graph
 
	transition: A*S
	
	Example:
	let e = [1, 0]': i.e., ending at q1
	 
	Do one step transition:
	A*e = 
	[p(q1|q1)*(q*|q1)+p(q2|q1)*p(q*|q2) p(q1|q2)*p(q*|q1)+p(q2|q2)*p(q2|q*)]' = [p(q*|q1) p(q*|q2)]'

	at the end of transition, the matrix contains the probability of
	ending at q*, starting at q_x
	given q_x has a starting prior p(x), p(q_x|q*) = p(q*|q_x)p(x)/p(q*)
	
	To add the prior, construct a vector x = [p(q1), p(q2)]
	After n-steps, dot product the prior to the final vector
	A^n*e.*x' 
	 = [p(q1|q1)*p(q1) p(q1|q2)*p(q2)]'
	
	Note: the final result is a column vector
	"""
	def backward_walk(self, end_prob, steps):
		init = self.A*end_prob
		for s in range(steps-1):
			init = self.A*init
		return init
	
